#include "stdafx.h"
#include "polygon2d.h"

// Test the orientation of a simple polygon
// Return:	>0 for counterclockwise
//			=0 for none(degenerate)
//			<0 for clockwise
// Note: this algorithm is faster than computing the signed area
double geometry::Polygon2D::Orientation(void) const
{
	int n = Size();
	if(n<3) return 0;

	vertexes.push_back(vertexes[0]);

	// First find rightmost lowest vertex of the polygon
	int rmin = 0;
	double xmin = vertexes[0].x_;
	double ymin = vertexes[0].y_;
	for(int i=1; i<n; ++i) {
		if(vertexes[i].y_>ymin) continue;
		if(vertexes[i].y_==ymin && vertexes[i].x_<xmin) continue; // Just as low and to left

		rmin = i;
		xmin = vertexes[i].x_;
		ymin = vertexes[i].y_;
	}

	// Test orientation at this rmin vertex
	// CCW <=> the edge leaving is left of the entering edge
	double temp = 0;
	if(rmin==0) {
		temp = vertexes[1].IsLeft(vertexes[n-1], vertexes[0]);
	} else {
		temp = vertexes[rmin+1].IsLeft(vertexes[rmin-1], vertexes[rmin]);
	}

	vertexes.pop_back();
	return temp;
}

double geometry::Polygon2D::Area(void) const
{
	int n = Size();
	if(n<3) return 0;

	vertexes.push_back(vertexes[0]);
	vertexes.push_back(vertexes[1]);

	double area = 0;
	for(int i=1, j=2, k=0; i<=n; ++i, ++j, ++k) {
		area += vertexes[i].x_*(vertexes[j].y_-vertexes[k].y_);
	}

	vertexes.pop_back();
	vertexes.pop_back();
	return area/2;
}

// Crossing number test for a point in a polygon(WRF)
bool geometry::Polygon2D::PtIn_CN_WRF(const Point2D& pt) const
{
	bool bin = false;
	int nvert = Size();
	for(int i=0, j=nvert-1; i<nvert; j=i++) {
		if(((vertexes[i].y_>pt.y_)!=(vertexes[j].y_>pt.y_))&&
      (pt.x_<(vertexes[j].x_-vertexes[i].x_)*(pt.y_-vertexes[i].y_)/(vertexes[j].y_-vertexes[i].y_)+vertexes[i].x_)) {
			bin = !bin;
		}
	}

	return bin;
}

// Crossing number test for a point in a polygon(JOR)
bool geometry::Polygon2D::PtIn_CN_JOR(const Point2D& pt) const
{
	bool bin = false;
	int nvert = Size();
	for(int i=0, j=nvert-1; i<nvert; j=i++) {
		if((((vertexes[i].y_<=pt.y_)&&(pt.y_<vertexes[j].y_))||
      ((vertexes[j].y_<=pt.y_)&&(pt.y_<vertexes[i].y_)))&&
      (pt.x_<(vertexes[j].x_-vertexes[i].x_)*(pt.y_-vertexes[i].y_)/(vertexes[j].y_-vertexes[i].y_)+vertexes[i].x_)) {
			bin = !bin;
		}
	}

	return bin;
}

// Crossing number test for a point in a polygon(JW)
bool geometry::Polygon2D::PtIn_CN_JW(const Point2D& pt) const
{
	bool bin = false;
	int nvert = Size();
	for(int i=0, j=nvert-1; i<nvert; j=i++) { // Edge from vertexes[j] to vertexes[i]
		if(vertexes[j].y_<=pt.y_) {
			if(vertexes[i].y_>pt.y_ && pt.IsLeft(vertexes[j], vertexes[i])>0) {
				bin = !bin;
			}
		} else {
			if(vertexes[i].y_<=pt.y_ && pt.IsLeft(vertexes[i], vertexes[j])>0) {
				bin = !bin;
			}
		}
	}

	return bin;
}

// Winding number test for a point in a polygon
bool geometry::Polygon2D::PtIn_WN(const Point2D& pt) const
{
	int wn = 0;
	int nvert = Size();

	// loop through all edges of the polygon
	for(int i=0, j=nvert-1; i<nvert; j=i++) { // Edge from vertexes[j] to vertexes[i]
		if(vertexes[j].y_<=pt.y_) {
			if(vertexes[i].y_>pt.y_ && pt.IsLeft(vertexes[j], vertexes[i])>0) { ++wn; }
		} else {
			if(vertexes[i].y_<=pt.y_ && pt.IsLeft(vertexes[j], vertexes[i])<0) { --wn; }
		}
	}

	return wn!=0;
}